The present invention relates to a method of region filling and, more particularly, to a method of coloring a region of a frame buffer memory without the need to use any additional memory.
Graphic displays mapping frame-buffer memories are used in a wide range of fields such as the graphic user interface of computers. A color object which is displayed in such fields is formed from a plurality of picture elements or pixels each storing a single color. These color objects frequently include one or more filled regions. Examples of filled regions vary from simple shapes such as circles, ellipses and polygons, to more complicated planar regions resulting from projections or cuts of three dimensional bodies, which often includes one or more sub-regions of different colors (“holes”).
Many flood filling methods are known in the art and used in computer graphic applications as software routines, running on special purpose hardware devices that are called to perform certain graphic tasks including filling regions. These tasks are supplied in a library containing graphical functions that are typically delivered with a processing system so that users can write to displays with a higher level interface without having to know the complexity of any particular display and how to write to that display.
All known methods for filling a region require additional memory space (a stack) to be dedicated for the method, while performing the filling operation. The extra memory is used for “book-keeping” of the decisions which have been performed, so as to fill the entire region. For example, if at a certain step of the method a complete row of pixels have been processed (say, row number 10), and a decision has been made to move to a row above that row (row number 11), this decision must now be stored in the memory, so that in some later step the row below (row number 9) will be visited.
For an arbitrary region to be filled, the amount of memory that these methods require is not negligible, and it is comparable to the amount of memory used to store the region, i.e. it is proportional to the number of pixels in the region. To address this drawback, methods to reduce the stack size requirement, such as “pixel span approaches” have been suggested. For example, in an article entitled “An Efficient Flood-Filling Algorithm” written by S. V. Burtsev and Ye. R. Kuzmin, and published in 1993 in Computers & Graphics, (volume 17(5), pages 549–561), the authors provide a review of known filling algorithms and present a new boundary filling algorithm that requires space which is proportional to the horizontal dimension of the box containing the region. Other methods can be found e.g. in [D. Heam, M. Pauline Baker, “Computer Graphics”, Second Edition, Prentice Hall, 1994; Foley, van Dam, Feiner, Hughes, “Computer Graphics”, Second Edition in C, Addison Wesley, 1996].
In some computerized systems, an additional memory may not be available for performing the filling operation, hence the number of machines capable of performing these operations is limited. A typical industrial solution to a memory problem is to temporarily use external devices, such as hard drives and the like, to extend the available memory. However these solutions are slow and inefficient. An algorithm becomes unduly time consuming when users of graphical applications have to wait after they have selected the fill routine from a graphics library before the display screen displays the resulting filled region. It is important for customer satisfaction that the fill method is both fast and economic in terms of hardware requirement, without trading off the accuracy of the filled region.
There is thus a widely recognized need for, and it would be highly advantageous to have, a memory-free method of region filling devoid of the above limitation.